#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


class Node{
    public:
    int val;
    Node* next;
    Node* random;

    Node(int _val){
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution{
    public:
    unordered_map<Node*, Node*> cachedNode;

    Node* ans1(Node* head){
        if (head == nullptr) {
            return nullptr;
        }
        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = ans1(head->next);
            headNew->random = ans1(head->random);
        }
        return cachedNode[head];
    }

    Node* ans2(Node* head){
        Node* newhead = NULL;
        Node* newtail = NULL;
        Node* headtemp = head;
        while(headtemp){
            if(!newhead){
                newhead = newtail = new Node(headtemp->val);
                map[headtemp] = newhead;
                headtemp = headtemp->next;
            }else{
                newtail->next = new Node(headtemp->val);
                newtail = newtail->next;
                map[headtemp] = newtail;
                headtemp = headtemp->next;
            }
        }
        headtemp = head;
        Node* newheadtemp = newhead;
        while(headtemp){
            if(headtemp->random == NULL){
                newheadtemp->random = NULL;
            }else{
                newheadtemp->random = map[headtemp->random];
            }
            headtemp = headtemp->next;
            newheadtemp = newheadtemp->next;
        }
        return newhead;
    }

    private:
    unordered_map<Node*, Node*> map;
};

void test1(){
    Node* head = new Node(7);
    Node* head1 = new Node(13);
    Node* head2 = new Node(11);
    Node* head3 = new Node(10);
    Node* head4 = new Node(1);

    head->next = head1;
    head1->next = head2;
    head2->next = head3;
    head3->next = head4;

    head1->random = head;
    head2->random = head4;
    head3->random = head2;
    head4->random = head;

    Solution s;
    Node* ret1 = s.ans1(head);
    Node* ret2 = s.ans2(head);
    while(ret1 != NULL){
        cout << ret1->val << ends;
        cout << "   ptr:" << ret1 << "   next: " << ret1->next << "   random:" << ret1->random << endl;
        ret1 = ret1->next;
    }
    while(ret2 != NULL){
        cout << ret2->val << ends;
        cout << "   ptr:" << ret2 << "   next: " << ret2->next << "   random:" << ret2->random << endl;
        ret2 = ret2->next;
    }

}



int main(void){
    test1();

    return 0;
}